package com.dy.排序.内排序.插入排序.直接插入排序;

import com.dy.排序.内排序.RecordNode;
import com.dy.排序.内排序.SqlList;

import java.util.Arrays;

/*
将关键字的值插入到已经排好序的记录中，直到插完，时间复杂度 n^2/2,O(n^2)
空间复杂度O(1)

步骤：
 1、将r[i]暂存到temp中
 2、将temp与r[j](j=i-1....0)比较，若小于，将r[j]后移一个位置，然后插入
 3、将temp插入到r[j]上
 */
public class InsertSort {
    public  static void insertSort(RecordNode[] r){
        RecordNode temp;
        for(int i =1;i<r.length;i++){
            temp = r[i];
            int j=i-1;
            for(;j>=0;j--){
                if(temp.key.compareTo(r[j].key)<0){
                    r[j+1] = r[j];
                }
            }
            r[j] = temp;
        }
    }
//没有监视哨的直接插入
    public  static void insertSort2(int[] r){
        int temp;
        for(int i =1;i<r.length;i++){
            temp = r[i];
            int j=i-1;
            for(;j>=0 &&temp<r[j];j--){
                    r[j+1] = r[j];
            }
            r[j+1] = temp;
        }
    }
//有监视哨的直接插入 略
    public static void main(String[] args) {
        int[] nums={3,2,4,1,5,6};
        insertSort2(nums);
        Arrays.stream(nums).forEach(System.out::println);
    }
}
